/*
 @coding  : utf-8
 @Time    : 2023/5/23 14:51
 @Author  : Rumou
 @File    : 20230523-二叉树遍历.go
 @Description:
*/

package main

import "fmt"

// TreeNode 二叉树结构体
type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

// PreorderTraversal 前序遍历：根节点 -> 左子树 -> 右子树
func PreorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Println(root.Data)
	PreorderTraversal(root.Left)
	PreorderTraversal(root.Right)
}

// InorderTraversal 中序遍历：左子树 -> 根节点 -> 右子树
func InorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	InorderTraversal(root.Left)
	fmt.Println(root.Data)
	InorderTraversal(root.Right)
}

// PostorderTraversal 后序遍历：左子树 -> 右子树 -> 根节点
func PostorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	PostorderTraversal(root.Left)
	PostorderTraversal(root.Right)
	fmt.Println(root.Data)
}

func main() {
	tree := &TreeNode{
		Data: 1,
		Left: &TreeNode{
			Data: 2,
			Left: &TreeNode{
				Data:  4,
				Left:  nil,
				Right: nil,
			},
			Right: nil,
		},
		Right: &TreeNode{
			Data: 3,
			Left: nil,
			Right: &TreeNode{
				Data:  5,
				Left:  nil,
				Right: nil,
			},
		},
	}

	fmt.Println("前序遍历:")
	PreorderTraversal(tree)

	fmt.Println("中序遍历:")
	InorderTraversal(tree)

	fmt.Println("后序遍历:")
	PostorderTraversal(tree)
}
